#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include "bignum/bn.h"

//#define INPUT

#define LL long long

LL PowerMod(LL a, LL b, LL mod);

int test()
{
    int A, B, C;
    srand(time(NULL));
    int t = time(NULL);

#ifndef INPUT
    for (int i = 0; i < 100000; ++i)
    {   
        A = rand();
        B = rand() + 1;
        C = rand() + 1;
#endif
        
#ifdef INPUT
        while(scanf("%d%d%d", &A, &B, &C) != EOF)
        {
#endif
        BigNumber a(BigNumber::ValueOf(A));
        BigNumber b(BigNumber::ValueOf(B));
        BigNumber c(BigNumber::ValueOf(C));
        
         int err = 0;

       /* if (A + B != int(a + b)){
            err = 1;
            printf("a + b = %d %d\n", A + B, int(a + b));
        }

        if (A - B != int(a - b)){
            err = 1;
            printf("a - b = %d %d\n", A - B, int(a - b));
        }

        if (A * B != int(a * b)){
            err = 1;
            printf("a * b = %d %d\n", A * B, int(a * b));
        }

        if (A / B != int(a / b)){
            err = 1;
            printf("a / b = %d %d\n\n\n\n", A / B, int(a / b));
        }*/
    
         if (int(PowerMod(a, b, c)) != int(BigNumber::ExpMod(a, b, c))){
             err = 1;
             printf("(a^b) % c = %s\n", std::string(BigNumber::ExpMod(a, b, c)).c_str());
         }
        

        if (err){
            printf("a=%d\t\tb=%d\t\t%d\n", A, B, C);
        }
    }

#ifndef INPUT
    printf("%d\n", time(NULL) - t);
#endif
    return 0;
}

//32310 15